You need to construct a binary tree from a string consisting of parenthesis and integers.
The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
You always start to construct the left child node of the parent first if it exists.
Example 1:
Input: s = "4(2(3)(1))(6(5))" Output: [4,2,6,3,1,5]
Example 2:
Input: s = "4(2(3)(1))(6(5)(7))" Output: [4,2,6,3,1,5,7]
Example 3:
Input: s = "-4(2(3)(1))(6(5)(7))" Output: [-4,2,6,3,1,5,7]
Constraints:
0 <= s.length <= 3 * 104sconsists of digits,'(',')', and'-'only.
Average Rating: 4.69 (13 votes)
Solution
Overview
This is a really useful problem to work on since this is a part of the general umbrella of problems which are like Serialize and Deserialize some data structure. This is important if we want to save a tree (a custom object with some special properties and fields) to a file, a database, or as a string someplace essentially. In this problem we are given a string representation of a tree i.e. we are given the serialized version of the tree and we have to deserialize it and return the TreeNode object representing the root of the tree (since the rest of the tree is trackable via the root).
A tree (or a graph) has a recursive structure to it i.e. a subtree is a tree in itself. Similarly, we expect the string representation of a tree to also have some kind of a recursive structure and that is what will be used to reconstruct our tree. Let's first take a look at this recursive structure in the string.
Figure 1. The tree and the corresponding string.
Let's look at the subtrees along with their counterparts in the string. Note that we assume the entire string is also enclosed between a pair of brackets thus representing the entire tree.
Figure 2. String split according to the subtrees.
So we can see the recursive build-up of the string and we are going to leverage that property to come up with a solution. Since this problem involves a recursive property, we will look at a solution based on recursion, and then, we will convert that solution to one using a stack as opposed to the memory stack used in the recursive approach.
Approach 1: Recursion
Intuition
The idea here is very simple. An opening bracket represents the start of a new tree (subtree really). Thus, whenever we encounter a new opening bracket, we make a new recursion call. A recursion call to our function will essentially return the root of a properly built tree with all the required TreeNode objects and proper connections set up between them. Thus, making a new recursive call upon encountering an opening bracket is essentially calling our function to build the subtree and return the root node.
We know when to make a new recursive call, but, when do we stop really? We stop when we encounter a closing bracket. That's because a closing bracket will be the end of the most recent subtree that we're building in our recursion. We assume that a particular closing bracket matches with the nearest opening bracket we would have encountered previously when we made the recursive call. Let's put all this information into an algorithm with steps.
Algorithm
-
Let's define a couple of internal functions that we will be using along the way. The first one is called
getNumberand it returns the integer number/value that the currentTreeNodeis supposed to have. It takes the string and the current index as inputs. We iterate until we no longer encounter a digit or we reach the end of the string. We stick all the digits together and get a number. Also, we take care of the sign-in case one exists in the beginning which would indicate a negative value for the node. -
The next function we define is our recursive function called
str2treeInternalwhich does all the heavy lifting for us. It also takes the string and the index of the current character as inputs and returns a pair of theTreeNoderepresentation of the current subtree and also the index of the next character to be processed in the string. This index manipulation is important because we don't want to parse the string twice to figure out the boundaries for the children subtrees. -
Whenever the function
str2treeInternalis called, we expect that the current subtree will all its children and descendants will be constructed and returned. There are 4 steps we take inside this function of ours.-
Firstly we check for the termination condition i.e. if there are no more characters left in the string to process.
Figure 3. Sample subtrees which we will consider for the algorithm.
-
Next, we get the value for the root node of this tree. This is an invariant here. We will never find any brackets before we get the value for the root node.
-
Once we have the value, we form the root node.
-
Then, we check for an opening bracket (make sure to check for the end of string conditions always). If there is one, we make a recursive call and use the node returned as the left child of the current node.
-
Finally, we check if there's another opening bracket. If there is one, then it represents our right child and we again make a recursive call to construct that and make the right connection.
-
-
We return the construct root node and also the correct index. For the index, we check if it points to a closing bracket, we move one step forward. Else, we stay at the current spot and let the caller function decide how to proceed/process.
Implementation
Complexity Analysis
-
Time Complexity: O(N) where N represents the number of characters in the string representation. This is because each character is processed exactly once and we need to process the entire string to form our tree.
-
Space Complexity: O(H) where H represents the height of the tree. We don't have any information about if the tree is balanced or not and so, in the worst case when the tree would be skewed left (can't be right according to the problem), we will have a recursion stack consisting of N calls and hence, the overall space complexity can be O(N);
Approach 2: Stack
Intuition
The main problem with a recursive solution is the stack limitation. We might run into stack-overflow problems if the tree is too tall and the system's stack is low on resources. Hence, we prefer to use our own stack and that is the variation which we will explore in this solution. The overall idea remains the same as the previous approach and for that matter, even the complexities remain the same. The only thing that changes is a recursive vs iterative approach.
The algorithm presented here is completely based on the recursive solution before. The only thing we need to take care of are the different states a particular function call/node can be in during recursion. Notably, there are 3 different states that we need to account for. We won't be using these three states in the code directly but it is important to understand these three possibilities to understand the overall algorithm.
- NOT_STARTED ~ This is the initial state that a node is in. Before we even process the left or the right children. In this state, we simply form the value of the root node and then check for the presence of the left child. If the left child exists, we make a recursive call and the returned value is used as the left child.
- LEFT_DONE ~ In this state, we are processing our root node given the fact that we're done processing its left subtree. So, the
indexwould be used to check for the presence of a right child and if one exists, we make another recursive call to process the same. - RIGHT_DONE ~ This is the final state of any node where we are done processing the left and the right children and don't need to do anything more.
Algorithm
- Let's define a function called
getNumberwhich returns the integer number/value that the currentTreeNodeis supposed to have. It takes the string and the current index as inputs. We iterate until we no longer encounter a digit or we reach the end of the string. We stick all the digits together and get a number. Also, we take care of the sign-in case one exists in the beginning which would indicate a negative value for the node. - We use a
stackfor our implementation and it would contain a pair of the node itself and the state it is in. The state can be one of the three described before. - Initially, we push the
root node(a newTreeNodeessentially) into the stack. Note: that the state of this node isNOT_STARTED. - We iterate over the characters in our string one by one and we do the following at each step:
-
Pop the node. This will be the root node that we currently process i.e. not the global root node of the tree but rather the root of the current subtree.
-
If the current character pointed to by the
indexis a digit or the-character,- that means we have a node that we haven't started processing yet i.e. the
NOT_STARTEDstate. So the first thing we do is to call thegetNumberfunction to get the value for the node and setnode.valto this value. Note: thegetNumberfunction progresses theindex. - Then, we check for the presence of a left child. We simply check if there are more characters left in the string and the one we have to process now is an opening bracket. If it is, then we do two things:
-
We add the current node back to the queue. At this point, the state of this node would be
LEFT_DONE. Again, we don't need the state information anywhere in the code except for reasoning about the algorithm itself. -
Then, we assign
node.leftto a newTreeNodeand also add it to the queue.Figure 4. Process the root node from the string.
Figure 5. Here we process the left child.
Figure 6. Complete the processing or the left child.
-
- that means we have a node that we haven't started processing yet i.e. the
-
If the current character is the left bracket i.e.
(,- we check for the presence of a right child because we know that the value of the node is already set in the previous step and also, the left child is properly processed at this point.
- We check if the current character, if there is one left, is an opening bracket. If it is one then we do the following:
-
We add the current node back to the queue assuming its state to be
LEFT_DONE. -
Then, we assign
node.rightto a newTreeNodeand also add it to the queue.Figure 7. Start processing the right child.
-
-
We don't do anything if the current character is a closing bracket except for popping the nodes which we already did in step
4.1here.Figure 8. Pop the right child and return the root.
-
Implementation
Complexity Analysis
The complexity is the same as the previous solution with the only exception that we are now using our own stack instead of relying on the system's stack.
-
Time Complexity: O(N) where N represents the number of characters in the string representation. This is because each character is processed exactly once and we need to process the entire string so as to form our tree.
-
Space Complexity: O(H) where H represents the height of the tree. We don't have any information about if the tree is balanced or not and so, in the worst case when the tree would be skewed left (can't be right according to the problem), we will have a recursion stack consisting of N calls and hence, the overall space complexity can be O(N);
Easy to understand recursion approach
public class Solution {
private int index = 0;
public TreeNode Str2tree(string s) {
index = 0;
return BuildTree(s);
}
private TreeNode BuildTree(string str){
//This is our condition to come out of recurssion
if(index >= str.Length) return null;
//If current character is closed bracket ')'
//This means child of the node which called recurrsion is null
// Also increament the index, to process the next character.
if(str[index] == ')'){
index++;
return null;
}
int val = GetValue(str);
var node = new TreeNode(val);
//Check if we have not reached end of string,
//If we have open bracket, means we need to add left child first.
//So, call BuildTree to add left child from current position.
if(index < str.Length && str[index] =='(')
{
index++;
node.left = BuildTree(str);
}
//Check if we have not reached end of string,
//If we have open bracket, means we need to add right child.
//So, call BuildTree to add right child from current position.
if(index < str.Length && str[index] =='(')
{
index++;
node.right = BuildTree(str);
}
//Increase the index, to get pass the closed bracket for the current sub-tree.
index++;
//Return the node created.
return node;
}
private int GetValue(string str)
{
var valueStr = new StringBuilder();
//Get all possible numerical characters including -ve
while(index < str.Length && str[index] != ')' && str[index] != '(')
valueStr.Append(str[index++]);
//Parse the numerical value.
return Int32.Parse(valueStr.ToString());
}
}
Hope this helps someone :)
So does this problem not allow for NULL nodes like in https://leetcode.com/problems/construct-string-from-binary-tree/ ? Confusing how its worded.
Ie. This is an invalid test case according to the console "1(2()(4))(3)"
Last Edit: March 16, 2021 9:10 AM
Clean python 3 O(N) with iterator
class Solution:
def str2tree(self, s: str) -> TreeNode:
def build(I) -> TreeNode:
num = ''
while (nxt := next(I)) not in '()':
num += nxt
node = TreeNode(int(num))
if nxt == '(':
node.left = build(I)
if next(I) == '(':
node.right = build(I)
next(I) # skip tail ')'
return node
return build(iter(s + ')')) if s else None
For solution 1, it was quite confusing because there is no reason why:
- We need to check for the left node when building the right. Problem says the left node will always be populated first. I can see why to include it to make the problem more generalized (possibly), but this check is not needed.
- At the end of the helper function, we should always return i + 1. I did not find an example that needed return index.
Recursion with Nodes and constructing from ground
Deserialization
class Solution:
def str2tree(self, s: str) -> TreeNode:
def deserialize(s):
elems = [s[:2]]
s = s[2:]
val = 0
for i, j in enumerate(s):
if j=='(':
val+=1
elif j==')':
val-=1
if val==-1:
return ''.join(elems)[1:], s[i+2:-1]
elems.append(j)
return ''.join(elems)
def recFun(s):
[#s](https://leetcode.com/problems/two-sum) = "4(2(3)(1))(6(5))"
if s=='':
return None
if '(' not in s:
return TreeNode(int(s))
n= s.split('(')[0]
pr = '('+'('.join(s.split('(')[1:])
node = TreeNode(int(n))
a,b = deserialize(pr)
node.left = recFun(a)
node.right = recFun(b)
return node
node = recFun(s)
return node
April 23, 2021 11:03 AM
If you feel the code of the solution is so complex.
Please check https://leetcode.com/problems/construct-binary-tree-from-string/discuss/1172375/Java-O(N)-time-Explanation
April 18, 2021 10:42 AM
I sort of took a different approach with my stack solution:
class Solution {
public:
TreeNode* str2tree(string s) {
if(s == "") return nullptr;
stack<string> process;
stack<pair<TreeNode*,int>> nodes;
s = "(" + s + ")";
int level = 0;
int n = s.length();
string cur = "";
for(int i=0; i<n; i++)
{
if(s[i] == '(')
{
if(cur != "") process.push(cur);
cur = "";
level++;
}
else if(s[i] == ')')
{
string num = cur;
if(num == "")
{
num = process.top();
process.pop();
}
TreeNode* node = new TreeNode(stoi(num));
vector<TreeNode*> children;
while(!nodes.empty() && level < nodes.top().second)
{
if(node->right) node->left = nodes.top().first;
else node->right = nodes.top().first;
nodes.pop();
}
if(node->left == nullptr && node->right)
{
node->left = node->right;
node->right = nullptr;
}
nodes.push({node, level});
cur = "";
level--;
}
else
{
cur += s[i];
}
}
return nodes.top().first;
}
};
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* str2tree(string s) { }};









